Entropy encoding/decoding is a technique to represent an arbitrary data set by using fewer data bits. Entropy encoding uses a data probability context based on observed statistical distributions of prior processed data symbols. The probability context provides allows fairly accurate predictions of symbols to be encoded/decoded. Adaptive versions of entropy coders are able to build up probability data and update it over the course of large files. Popular entropy encoding algorithms to produce bit sequences are Huffman coding and arithmetic encoding. Arithmetic encoding does not pose the limitations on the probabilities that are associated with Huffman coding. The term arithmetic encoding can refer to a broad class of entropy encoders which include range coders and Huffman coders. It may also refer to a unique sub-set of this broad class of entropy encoders. Huffman coding and range coding are really just special cases of arithmetic coding.
Practical arithmetic encoders operate by having a data register, often referred to as an accumulator, that performs the arithmetic required to encode a source data stream. Source data streams are often accepted by an encoder as data symbols of a fixed number of bits that are a small subset of the entire data stream to be encoded. Input data symbols are processed individually and intermediate calculation values are maintained in the accumulator. As more input symbols are processed, the values of state variables used by the encoding process, such as the output data stream value and encoding range for the next input data symbol, become incompatible with the fixed size of the accumulator. In order to accommodate these incompatible values of state variables, processing is occasionally performed to “renormalize” these values. Encoding processing often determines if renormalization is required after processing each input data symbol. The processing to determine the need to renormalize the state variables is therefore frequently performed by the encoding process and improving efficiencies in this determination have a great effect on the performance of the arithmetic encoder.
Accordingly, what is needed in this art is an entropy encoder/decoder with an efficient technique to determine the need to renormalize state variables and to efficiently perform such renormalization.